package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/17 19:19
 *
 字符流中第一个不重复的字符

 "google" out:"ggg#ll"

"abcdee"  out:"aaaaaa"


自己想的：链表维护字符串+set用于判断是否重复 O(n^2-----如果是自己实现的链表就是O(n))
题解：1，维护字符串（与链表功能一样）+哈希表,然后直接遍历字符串比对即可
2,队列+哈希表
 */

import java.util.*;

public class Main36 {
    Queue<Character>queue=new LinkedList<>();
    HashMap<Character,Integer>map=new HashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch) {
        queue.add(ch);
        if(map.containsKey(ch)){
            map.put(ch,map.get(ch)+1);
        }else{
            map.put(ch,1);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        while(!queue.isEmpty()){
            char ch=queue.peek();
            if(map.get(ch)==1){
                return ch;
            }else {
                queue.poll();
            }
        }
        return '#';
    }
    /*
    List<Character>list=new LinkedList<>();
    HashSet<Character>vis=new HashSet<>();
    //Insert one char from stringstream
    public void Insert(char ch) {
        boolean flag=true;
        for(int i=0;i<list.size();++i){
            if(list.get(i)==ch){
                list.remove(i);
                flag=false;
                vis.add(ch);
                break;
            }
        }
        if(flag&&!vis.contains(ch)){
            System.out.println(ch);
            list.add(ch);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        return list.size()==0?'#':list.get(0);
    }
    */

    public static void main(String[] args) {
        List<Integer>list=new LinkedList<>();
        list.get(0);
    }
}
